#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#include <vector>

//class Solution {
//public:
//    void duplicateZeros(vector<int>& arr) {
//        int dest = -1;
//        int cur = 0;
//        while (dest < (int)arr.size() - 1)
//        {
//            if (arr[cur] != 0)
//            {
//                dest++;
//            }
//            else
//            {
//                dest += 2;
//            }
//            cur++;
//        }
//
//        while (cur > 0)
//        {
//            if (arr[cur] == 0)
//            {
//                if (dest < arr.size())
//                    arr[dest] = 0;
//                arr[dest - 1] = 0;
//                dest -= 2;
//            }
//            else
//            {
//                arr[dest] = arr[cur];
//                dest--;
//            }
//            cur--;
//        }
//    }
//};
//class Solution {
//public:
//    void duplicateZeros(vector<int>& arr)
//    {
//        int dest = -1, cur = 0, n = arr.size() - 1;
//        while (cur <= n)
//        {
//            if (arr[cur])
//                dest++;
//            else
//                dest += 2;
//            if (dest >= n)break;
//            cur++;
//        }
//
//        while (cur >= 0)
//        {
//            if (arr[cur])
//            {
//                arr[dest--] = arr[cur--];
//            }
//            else
//            {
//                if (dest < n)
//                    arr[dest] = 0;
//                arr[dest - 1] = 0;
//                dest -= 2;
//                cur--;
//            }
//        }
//    }
//};
//int main()
//{
//    vector<int> arr = { 1,0,7,2,4,3,1,0,2,6 };
//    Solution().duplicateZeros(arr);
//    return 0;
//}

#include <algorithm>
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        for (int i = 0; i < nums.size() - 2; i++)
        {
            int left = i + 1, right = nums.size() - 1;
            while (left < right)
            {
                int sum = nums[left] + nums[right];
                if (sum > -nums[i])
                {
                    right--;
                }
                else if (sum < -nums[i])
                {
                    left++;
                }
                else
                {
                    ret[ret.size()] = { nums[i],nums[left],nums[right] };
                    int t = left;
                    while (left < right && nums[t] == nums[left])
                    {
                        left++;
                    }
                    t = right;
                    while (left < right && nums[t] == nums[right])
                    {
                        right--;
                    }
                }
            }
            while (i < nums.size() - 2 && nums[i] == nums[i + 1])
            {
                i++;
            }
        }
        return ret;
    }
};
int main()
{
    vector<int> num = { 1,0,1,2,-1,4 };
    Solution().threeSum(num);
    return 0;
}